

#include "stdafx.h"

#include "Utils.h"


#define M 7

int sq[M] = { 1, 7, 3, 5, 9, 4, 8 };
int maxLen[M] = { 0 };
int sqIdx[M] = { 0 };

#ifdef TEST_BED
int main()
#else
int main_()
#endif
{
	//step1. init
	maxLen[0] = 1;
	for (int i = 1; i < M; i++)
		sqIdx[i] = -1;

	//step2. recursion formula
	for (int i = 1; i < M; i++) {
		//sq[i]
		int maxVal = 0;
		for (int j = 0; j < i; j++) {
			//sq[j]
			if (sq[j] < sq[i]) {
				maxVal = MAX(maxLen[j], maxVal);
				sqIdx[i] = j;
			}
		}
		maxLen[i] = maxVal + 1;
	}

	printf("max rise subsequence len of sq is %d\n", maxLen[M - 1]);

	printf("Path of index of %d is: \n", M - 1);

	int stack[M] = { 0 };

	int i = 0;
	int idx = M - 1;
	stack[i] = idx;
	do {
		idx = sqIdx[idx];
		stack[++i] = idx;
	} while (idx > 0);

	for (int j = i; j >= 0; j--)
		printf("%d ", stack[j]);


    return 0;
}

#if 0

//step1. init
maxLen[0] = 1;

//step2. recursion formula
for (int i = 1; i < M; i++) {
	//sq[i]
	int maxVal = 0;
	for (int j = 0; j < i; j++) {
		//sq[j]
		if (sq[j] < sq[i]) {
			maxVal = MAX(maxLen[j], maxVal);
		}
	}
	maxLen[i] = maxVal + 1;
}

printf("max rise subsequence len of sq is %d\n", maxLen[M - 1]);

#endif

